package 笔试.网易笔试.第四题动态规划贴瓷砖;

public class Main
{
    public static void main(String[] args)
    {
        //动态规划，当前问题由更多的子问题组成，子问题之间有相互重叠的部分，
        //看最后一块/第一块的摆放情况，有3种情况，分别剩下n-1,n-2,n-3
        System.out.println(method(4));
    }
    public static int method(int n)
    {
        if (n==0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)
            return 2;
        if (n==3)
            return 4;
        int fminusone=4;
        int fminustwo=2;
        int fminusthree=1;
        int fN=0;
        for (int i = 4; i <= n; i++)
        {
            fN=fminusone+fminustwo+fminusthree;
            fminusthree=fminustwo;
            fminustwo=fminusone;
            fminusone=fN;

        }
        return fN;
    }
}
